import java.util.Arrays;

public class HeapSort {
    private int[] array;
    public HeapSort(int[] array){
        this.array=array;
    }
    public void print(){
        for (int i = 1; i <= array.length-1; i++) {
            System.out.print(array[i]+"\t");
        }
    }
    public void swap(int []arr,int a ,int b){
        int temp=arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }
    public void Sort(){
        BuildHeap(array,array.length);
        for (int i = array.length-1; i > 0; i--) {
            swap(array,0,i);
            HeapMaintenance(array,0,i);
        }
    }

    private void BuildHeap(int[] a,int len){
        for (int i = len/2-1; i >=0 ; i--) {
            HeapMaintenance(a,i,len);
        }
    }

    private void HeapMaintenance(int[] a,int k,int len){
        int tmp=a[k];
        for (int j = 2*k+1; j < len; j*=2+1) {
            if(j+1<len&&a[j]<a[j+1])
                j++;
            if(tmp>=a[j]) break;
            else{
            a[k]=a[j];
            k=j;}
        }
        a[k]=tmp;
    }
}
